We give the first nontrivial upper bounds on the Boolean average sensitivity and noise sensitivity of degree-$d$ polynomial threshold functions (PTFs). Our bound on the Boolean average sensitivity of PTFs represents the first progress toward the resolution of a conjecture of Gotsman and Linial [Combinatorica, 14 (1994), pp. 35--50], which states that the symmetric function slicing the middle $d$ layers of the Boolean hypercube has the highest average sensitivity of all degree-$d$ PTFs. Via the $L_1$ polynomial regression algorithm of Kalai et al. [SIAM J. Comput., 37 (2008), pp. 1777--1805], our bound on Boolean noise sensitivity yields the first polynomial-time agnostic learning algorithm for the broad class of constant-degree PTFs under the uniform distribution. To obtain our bound on the Boolean average sensitivity of PTFs, we generalize the “critical-index” machinery of [R. Servedio, Comput. Complexity, 16 (2007), pp. 180--209] (which in that work applies to halfspaces, i.e., degree-1 PTFs) to general PTFs. Together with the “invariance principle” of [E. Mossel, R. O'Donnell, and K. Oleszkiewicz, Ann. of Math. (2), 171 (2010), pp. 295--341], this allows us to essentially reduce the Boolean setting to the Gaussian setting. The main ingredients used to obtain our bound in the Gaussian setting are tail bounds and anticoncentration bounds on low-degree polynomials in Gaussian random variables [S. Janson, Gaussian Hilbert Spaces, Cambridge University Press, Cambridge, UK, 1997; A. Carbery and J. Wright, Math. Res. Lett., 8 (2001), pp. 233--248]. Our bound on Boolean noise sensitivity is achieved via a simple reduction from upper bounds on average sensitivity of Boolean PTFs to corresponding bounds on noise sensitivity.
展开▼
机译:我们给出度-$ d $多项式阈值函数(PTF)的布尔平均灵敏度和噪声灵敏度的第一个非平凡的上限。我们对PTF的布尔平均敏感度的界限代表了解决Gotsman和Linial猜想的第一个进展[Combinatorica,14(1994),第35--50页],其中指出对称函数将中间的$ d切片布尔超立方体的$层在所有度-dd $ PTF中具有最高的平均灵敏度。通过Kalai等人的$ L_1 $多项式回归算法。 [SIAM J. Comput。,37(2008),第1777--1805页],我们对布尔噪声敏感度的约束产生了在均匀分布下针对广泛类别的恒定度PTF的第一个多项式时间不可知学习算法。为了获得对PTF布尔平均敏感度的界线,我们对[R. Servedio,计算机。复杂性,16(2007),pp。180--209](在该工作中适用于半空间,即1级PTF)到通用PTF。连同[E. Mossel,R.O'Donnell和K.Oleszkiewicz,安。数学。 (2),171(2010),pp。295--341],这使我们能够将布尔值设置实质上简化为高斯设置。在高斯环境中用于获得界的主要成分是高斯随机变量中低阶多项式的尾界和反集中界[S.詹森,高斯希尔伯特空间,剑桥大学出版社,英国剑桥,1997年; A. Carbery和J. Wright,数学。 Res。 Lett。,8(2001),233--248页]。通过将布尔PTF的平均灵敏度的上限简单地降低到噪声灵敏度的相应范围,可以达到我们对布尔噪声灵敏度的限制。
展开▼